from typing import List


class Solution:
    """
    改用类似dp的思路，只是通常的dp是1个1个递增，对空间占有率较高。
    先尝试看看。
    速度72%，且算是大多数人的较高水平了，先这样
    """
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[-1]*(amount+1)
        dp[0]=0
        for i in range(1,len(dp)):
            for coin in coins:
                if i>=coin and dp[i-coin]!=-1:
                    new_count=dp[i-coin]+1
                    dp[i]=new_count if dp[i]==-1 else min(dp[i],new_count)
        # print(dp)
        return dp[-1]
    

if __name__=='__main__':
    coins=[186,419,83,408]
    amount=6249
    # coins = [1, 2, 5] 
    # amount = 11

    s=Solution()
    res=s.coinChange(coins,amount)
    print(res)